{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Duplicate Subtrees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #hash-table #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #哈希表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findDuplicateSubtrees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找重复的子树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树的根节点 <code>root</code> ，返回所有 <strong>重复的子树 </strong>。</p>\n",
    "\n",
    "<p>对于同一类的重复子树，你只需要返回其中任意 <strong>一棵 </strong>的根结点即可。</p>\n",
    "\n",
    "<p>如果两棵树具有<strong> 相同的结构</strong> 和 <strong>相同的结点值 </strong>，则认为二者是 <strong>重复 </strong>的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/16/e1.jpg\" style=\"height: 236px; width: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,4,null,2,4,null,null,4]\n",
    "<strong>输出：</strong>[[2,4],[4]]</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/16/e2.jpg\" style=\"height: 125px; width: 200px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [2,1,1]\n",
    "<strong>输出：</strong>[[1]]</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/16/e33.jpg\" style=\"height: 202px; width: 300px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [2,2,2,3,null,3,null]\n",
    "<strong>输出：</strong>[[2,3],[3]]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的结点数在 <code>[1, 5000]</code> 范围内。</li>\n",
    "\t<li><code>-200 &lt;= Node.val &lt;= 200</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-duplicate-subtrees](https://leetcode.cn/problems/find-duplicate-subtrees/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-duplicate-subtrees](https://leetcode.cn/problems/find-duplicate-subtrees/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,null,2,4,null,null,4]', '[2,1,1]', '[2,2,2,3,null,3,null]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        def add(root: Optional[TreeNode]) -> Tuple:\n",
    "            if not root:\n",
    "                return None\n",
    "            key = (root.val, add(root.left), add(root.right))\n",
    "            subtree[key].append(root)\n",
    "            return key\n",
    "        \n",
    "        subtree = collections.defaultdict(list)\n",
    "        add(root)\n",
    "        ans = []\n",
    "        for _, val in subtree.items():\n",
    "            if len(val) > 1:\n",
    "                ans.append(val[0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findDuplicateSubtrees(self, root):\n",
    "        self.res = []\n",
    "        self.dic = {}\n",
    "        self.dfs(root)\n",
    "        return self.res\n",
    "    \n",
    "    def dfs(self, root):\n",
    "        if not root: return '#'\n",
    "        tree = self.dfs(root.left) + self.dfs(root.right) + str(root.val)\n",
    "        if tree in self.dic and self.dic[tree] == 1:\n",
    "            self.res.append(root)\n",
    "        self.dic[tree] = self.dic.get(tree, 0) + 1\n",
    "        return tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: 'TreeNode') -> 'List[TreeNode]':\n",
    "        ret = []\n",
    "        cache = {}\n",
    "        \n",
    "        def helper(root):\n",
    "            if root is None:\n",
    "                return '#'\n",
    "            else:\n",
    "                left = helper(root.left)\n",
    "                right = helper(root.right)\n",
    "                cur = str(root.val) + left + right\n",
    "                if cache.setdefault(cur, 0) == 1:\n",
    "                    ret.append(root)\n",
    "                cache[cur] += 1\n",
    "                return cur\n",
    "        helper(root)\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:\n",
    "        # 空树\n",
    "        if not root:\n",
    "            return []\n",
    "        # 线性树 - 单右枝树\n",
    "        elif not root.left:\n",
    "            has_left = False\n",
    "            while root.right:\n",
    "                root = root.right\n",
    "                if root.left:\n",
    "                    has_left = True\n",
    "                    break\n",
    "            if not has_left:\n",
    "                return []\n",
    "        # 线性树 - 单左枝树\n",
    "        elif not root.right:\n",
    "            has_right= False\n",
    "            while root.left:\n",
    "                root = root.left\n",
    "                if root.right:\n",
    "                    has_right = True\n",
    "                    break\n",
    "            if not has_right:\n",
    "                return []\n",
    "            \n",
    "        \n",
    "        def dfs(root, record):\n",
    "            \"\"\" 通过 DFS 遍历和记录树节点到哈希映射中 \"\"\"\n",
    "            if root:\n",
    "                record[root.val].append(root)\n",
    "                dfs(root.left, record)\n",
    "                dfs(root.right, record)\n",
    "        \n",
    "        def compare_subtree(root1, root2):\n",
    "            \"\"\" 通过递归比较两树是否完全相同 \"\"\"\n",
    "            if (not root1) and (not root2):\n",
    "                return True\n",
    "            elif ((not root1) or (not root2)) or (root1.val != root2.val):\n",
    "                return False\n",
    "            else:\n",
    "                return compare_subtree(root1.left, root2.left) and compare_subtree(root1.right, root2.right)\n",
    "        \n",
    "        hashmap = collections.defaultdict(list)  \n",
    "        dfs(root, hashmap)\n",
    "        \n",
    "        # 结果列表\n",
    "        result = []\n",
    "        # 遍历树节点值\n",
    "        for key in hashmap.keys():\n",
    "            nodes = hashmap[key]\n",
    "            nodes_num = len(nodes)\n",
    "            # 若值相同的节点不止一个, 则需要进行比较\n",
    "            if nodes_num > 1:\n",
    "                # 遍历值相同的节点\n",
    "                for i in range(nodes_num-1):\n",
    "                    done = False  # 是否发现过当前重复子树, 默认 False\n",
    "                    for j in range(i+1, nodes_num):\n",
    "                        # 若待比较节点非空且完全相同\n",
    "                        if nodes[i] and nodes[j] and compare_subtree(nodes[i], nodes[j]):\n",
    "                            # 若此前尚未发现过重复子树\n",
    "                            if not done:\n",
    "                                # 则添加相同子树之一到结果列表\n",
    "                                result.append(nodes[i])\n",
    "                                # 标记置为 True\n",
    "                                done = True\n",
    "                            # 其余相同子树全部置为 None\n",
    "                            nodes[j] = None\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, root):\n",
    "        if root is None:\n",
    "            return str(self.hash_map[\"#\"])\n",
    "        left = self.dfs(root.left)\n",
    "        right = self.dfs(root.right)\n",
    "        tree_str = left + \",\" + str(root.val) + \",\" + right\n",
    "        if tree_str not in self.hash_map:\n",
    "            self.hash_map[tree_str] = self.cnt\n",
    "            self.cnt += 1\n",
    "        t = self.hash_map[tree_str]\n",
    "        self.count[t] = self.count[t] + 1 if t in self.count else 1\n",
    "        if self.count[t] == 2:\n",
    "            self.ans.append(root)\n",
    "        return str(self.hash_map[tree_str])\n",
    "    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:\n",
    "        self.cnt = 1\n",
    "        self.hash_map, self.count = {\"#\": 0}, {0:0}\n",
    "        self.ans = []\n",
    "        self.dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:\n",
    "        self.res = []\n",
    "        self.dfs(root, {})\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, root, tmp):\n",
    "        if not root:\n",
    "            return '#'\n",
    "        path = (root.val, self.dfs(root.left, tmp), self.dfs(root.right, tmp))\n",
    "        if path in tmp and tmp[path] == 1:\n",
    "            self.res.append(root)\n",
    "        tmp[path] = tmp.get(path, 0) + 1\n",
    "        return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# class Solution:\n",
    "#     def findDuplicateSubtrees(self, root):\n",
    "#         d = collections.defaultdict(list)\n",
    "#         def dfs(root):\n",
    "#             if not root: return ''\n",
    "#             s = ' '.join((str(root.val), dfs(root.left), dfs(root.right)))\n",
    "#             d[s].append(root)\n",
    "#             return s\n",
    "#         dfs(root)\n",
    "#         return [l[0] for l in d.values() if len(l) > 1]\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.hash, self.count = {}, {}  # hash用来把子树映射成某个数字，count用来统计子树的个数\n",
    "        self.cnt = 1\n",
    "        self.res = []\n",
    "\n",
    "    def findDuplicateSubtrees(self, root):\n",
    "        if not root:\n",
    "            return root\n",
    "        self.dfs(root)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, root):\n",
    "        \"\"\"\n",
    "        :param root: 以root为根结点的子树\n",
    "        :return: 以root为根结点的子树的字符串表示，用'1'，'2'，'3'，'4'，'5' ... 来表示不同的子树\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"1\"  # 1表示空子树，随后的子树用2，3，4，5，...来表示\n",
    "        left, right = self.dfs(root.left), self.dfs(root.right)  # left和right都对应着某个数字\n",
    "        subtree = left + \" \" + str(root.val) + \" \" + right\n",
    "        if subtree not in self.hash:\n",
    "            self.cnt += 1\n",
    "            self.hash[subtree] = self.cnt  # 第一轮哈希映射，把树的字符串表示映射成某个数字\n",
    "        t = self.hash[subtree]\n",
    "        self.count[t] = self.count.get(t, 0) + 1  # 第二轮哈希映射，统计每棵子树出现的次数\n",
    "        if self.count[t] == 2:  # 出现次数刚好等于2时，把节点添加到res中，避免重复\n",
    "            self.res.append(root)\n",
    "        return str(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:\n",
    "        d = collections.defaultdict(int)\n",
    "        ans = []\n",
    "\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "            \n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "\n",
    "            t = ((node.val, l, r))\n",
    "            d[t] += 1\n",
    "            if d[t] == 2:\n",
    "                ans.append(node)\n",
    "            \n",
    "            return t\n",
    "        \n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:\n",
    "        trees = {}\n",
    "        count = {}\n",
    "        ans = []\n",
    "        def getuid(node):\n",
    "            if node:\n",
    "                tempkey = (node.val,getuid(node.left),getuid(node.right))\n",
    "                if tempkey not in count:\n",
    "                    count[tempkey] = 1\n",
    "                else:\n",
    "                    count[tempkey] += 1\n",
    "                if count[tempkey] == 2:\n",
    "                    ans.append(node)\n",
    "                return tempkey\n",
    "        getuid(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, node) -> string:\n",
    "\n",
    "        if node is None:\n",
    "            return \"\"\n",
    "\n",
    "        code_left = self.dfs(node.left)\n",
    "        code_right = self.dfs(node.right)\n",
    "\n",
    "        code = hash(str(node.val) + \"#\" + str(code_left) + \"*\" + str(code_right))\n",
    "        if code in self.subtrees and code not in self.res:\n",
    "            self.res[code] = node\n",
    "        self.subtrees.add(code)\n",
    "        return code\n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.subtrees = set()\n",
    "        self.res = {}\n",
    "        self.dfs(root)\n",
    "        return self.res.values()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "\n",
    "        seen = {}\n",
    "        idx = 0\n",
    "        repeat = set()\n",
    "\n",
    "        def dfs(node):\n",
    "\n",
    "            nonlocal idx\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            cur = (node.val, dfs(node.left), dfs(node.right))\n",
    "\n",
    "            if cur in seen:\n",
    "                node, index = seen[cur]\n",
    "                repeat.add(node)\n",
    "                return index \n",
    "            \n",
    "            else:\n",
    "                idx += 1\n",
    "                seen[cur] = (node, idx)\n",
    "                return idx\n",
    "\n",
    "        dfs(root)\n",
    "        #print(seen)\n",
    "        return list(repeat)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.index = 0\n",
    "        treesDic = {}\n",
    "\n",
    "        self.ans = []\n",
    "\n",
    "        def traverse(root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            tree = (root.val, traverse(root.left), traverse(root.right))\n",
    "            if tree in treesDic:\n",
    "                idx, seentime = treesDic[tree]\n",
    "                treesDic[tree] = (idx, seentime+1)\n",
    "                if seentime==1:\n",
    "                    self.ans.append(root)\n",
    "                return idx\n",
    "            else:\n",
    "                self.index += 1\n",
    "                treesDic[tree] = (self.index, 1)\n",
    "                return self.index\n",
    "        \n",
    "        traverse(root)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.seen = {}\n",
    "        self.idx_cnt = 0\n",
    "        self.duplicate = {}\n",
    "        self.dfs(root)\n",
    "        return self.duplicate.values()\n",
    "\n",
    "    def dfs(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        tri = (root.val, self.dfs(root.left), self.dfs(root.right))\n",
    "        if tri in self.seen:\n",
    "            idx = self.seen[tri]\n",
    "            if idx not in self.duplicate:\n",
    "                self.duplicate[idx] = root\n",
    "            return idx\n",
    "        self.idx_cnt += 1\n",
    "        self.seen[tri] = self.idx_cnt\n",
    "        return self.idx_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.d = {}\n",
    "        self.res = []\n",
    "        self.idx = 0\n",
    "\n",
    "    def post(self, root):\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        left_idx = None\n",
    "        right_idx = None\n",
    "        if root.left:\n",
    "            left_idx = self.post(root.left)\n",
    "        if root.right:\n",
    "            right_idx = self.post(root.right)\n",
    "\n",
    "        c = (root.val, left_idx, right_idx)\n",
    "\n",
    "        if c in self.d:\n",
    "            if self.d[c][1] == 0:\n",
    "                self.res.append(root)\n",
    "                self.d[c][1] += 1\n",
    "            return self.d[c][0]\n",
    "        else:\n",
    "            self.d[c] = [self.idx, 0]\n",
    "            self.idx += 1\n",
    "            return self.idx - 1\n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.post(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.index = 0\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        vis = dict()\n",
    "        duplicated = set()\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            else:\n",
    "                cur_tree = (node.val,dfs(node.left),dfs(node.right))\n",
    "                print(cur_tree)\n",
    "                if cur_tree in vis:\n",
    "                    idx,nd = vis[cur_tree]\n",
    "                    duplicated.add(nd)\n",
    "                    return idx\n",
    "                else:\n",
    "                    self.index +=1\n",
    "                    vis[cur_tree] = (self.index,node)\n",
    "                    return self.index\n",
    "\n",
    "        dfs(root)\n",
    "        return list(duplicated)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        def dfs(node: Optional[TreeNode]) -> int:\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            tri = (node.val, dfs(node.left), dfs(node.right))\n",
    "            if tri in seen:\n",
    "                (tree, index) = seen[tri]\n",
    "                repeat.add(tree)\n",
    "                print(\"repeat=\",repeat)\n",
    "                return index\n",
    "            else:\n",
    "                nonlocal idx\n",
    "                idx += 1\n",
    "                seen[tri] = (node, idx)\n",
    "   \n",
    "                return idx\n",
    "        \n",
    "        idx = 0\n",
    "        seen = {}\n",
    "        repeat = set()\n",
    "\n",
    "        dfs(root)\n",
    "    \n",
    "        return list(repeat)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        fe = {}\n",
    "        def build(root: Optional[TreeNode]):\n",
    "            if root is None:\n",
    "                return (0, 0, 0)\n",
    "            l, r  = build(root.left), build(root.right)\n",
    "            fe[root] = (max(l[0], r[0]) + 1, l[1] + r[1] + 1, l[1] - r[1])\n",
    "            return fe[root]\n",
    "        build(root)\n",
    "\n",
    "\n",
    "        def checkEq(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:\n",
    "            if (left is None) ^ (right is None):\n",
    "                return False\n",
    "            if left is None:\n",
    "                return True\n",
    "            if fe[left] != fe[right]:\n",
    "                return False\n",
    "            return left.val == right.val and checkEq(left.left, right.left) and checkEq(left.right, right.right)\n",
    "             \n",
    "        nodes = []\n",
    "        dups = []\n",
    "        def add(root: Optional[TreeNode]):\n",
    "            if root is None:\n",
    "                return\n",
    "            for n in nodes:\n",
    "                if checkEq(n[0], root):\n",
    "                    if not n[1]:\n",
    "                        dups.append(root)\n",
    "                        n[1] = True\n",
    "                    break\n",
    "            else:\n",
    "                nodes.append([root, False])\n",
    "            add(root.left)\n",
    "            add(root.right)\n",
    "        add(root.left), add(root.right)\n",
    "        return dups"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#     1\n",
    "#   2   3\n",
    "#  4 x 2 4\n",
    "# x x 4   \n",
    "# 当且仅当子树相同时，两棵树相同\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        counter = {}\n",
    "        ref = {}\n",
    "        def update(key,value):\n",
    "            counter.setdefault(key,[]).append(value)\n",
    "\n",
    "\n",
    "        def preiter(root):\n",
    "            yield (root.val)\n",
    "            # update((root.val,),root)\n",
    "            res = [root.val]\n",
    "            if root.left is not None:\n",
    "                res.append(tuple(preiter(root.left)))\n",
    "                yield from res\n",
    "            else:\n",
    "                res.append(None)\n",
    "                \n",
    "            if root.right is not None:\n",
    "                res.append(tuple(preiter(root.right)))\n",
    "                yield from res\n",
    "            else:\n",
    "                res.append(None)\n",
    "            update(tuple(res),root)\n",
    "\n",
    "        list(preiter(root))\n",
    "\n",
    "        res = []\n",
    "        for k,v in counter.items():\n",
    "            if len(v) > 1:\n",
    "                res.append(v[0])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#     1\n",
    "#   2   3\n",
    "#  4 x 2 4\n",
    "# x x 4   \n",
    "# 当且仅当子树相同时，两棵树相同\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        counter = {}\n",
    "        ref = {}\n",
    "        def update(key,value):\n",
    "            # print(key)\n",
    "            counter.setdefault(key,[]).append(value)\n",
    "            # val = counter.setdefault(key,0) + 1\n",
    "            # counter[key] = val\n",
    "            # ref.setdefault(key,[]).append(valu)\n",
    "            # ref[key] = value\n",
    "\n",
    "        def preiter(root,key=''):\n",
    "            yield (root.val, key)\n",
    "            # update((root.val,),root)\n",
    "            res = [root.val]\n",
    "            if root.left is not None:\n",
    "                res.append(tuple(preiter(root.left,'l')))\n",
    "                # update((root.val, *res),root.left)\n",
    "                yield from res\n",
    "            \n",
    "            if root.right is not None:\n",
    "                res.append(tuple(preiter(root.right,'r')))\n",
    "                # update((root.val, *res),root.right)\n",
    "                yield from res\n",
    "            update(tuple(res),root)\n",
    "\n",
    "        list(preiter(root))\n",
    "        \n",
    "        candidate = []\n",
    "        res = []\n",
    "        for k,v in counter.items():\n",
    "            if len(v) > 1:\n",
    "                res.append(v[0])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#     1\n",
    "#   2   3\n",
    "#  4 x 2 4\n",
    "# x x 4   \n",
    "# 当且仅当子树相同时，两棵树相同\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        counter = {}\n",
    "        ref = {}\n",
    "        def update(key,value):\n",
    "            counter.setdefault(key,[]).append(value)\n",
    "\n",
    "\n",
    "        def preiter(root,key=''):\n",
    "            yield (root.val, key)\n",
    "            # update((root.val,),root)\n",
    "            res = [root.val]\n",
    "            if root.left is not None:\n",
    "                res.append(tuple(preiter(root.left,'l')))\n",
    "                yield from res\n",
    "            \n",
    "            if root.right is not None:\n",
    "                res.append(tuple(preiter(root.right,'r')))\n",
    "                yield from res\n",
    "            update(tuple(res),root)\n",
    "\n",
    "        list(preiter(root))\n",
    "\n",
    "        res = []\n",
    "        for k,v in counter.items():\n",
    "            if len(v) > 1:\n",
    "                res.append(v[0])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.result = []\n",
    "        self.trees = dict()\n",
    "        self.treverse(root)\n",
    "        return self.result\n",
    "    \n",
    "    def treverse(self, root):\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        \n",
    "        left_tree = self.treverse(root.left)\n",
    "        right_tree = self.treverse(root.right)\n",
    "\n",
    "        tree = left_tree + \"|\" + right_tree + \"|\" + str(root.val)\n",
    "\n",
    "        n = self.trees.get(tree, 0)\n",
    "        if n == 1:\n",
    "            self.result.append(root)\n",
    "        \n",
    "        if tree in self.trees:\n",
    "            self.trees[tree] += 1\n",
    "        else:\n",
    "            self.trees[tree] = 1\n",
    "        return tree\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, root, tree_map):\n",
    "        if root == None:\n",
    "            return \"\"\n",
    "        res = str(root.val)\n",
    "        if root.left:\n",
    "            left_res = self.dfs(root.left, tree_map)\n",
    "            res = left_res + \"-\" + res\n",
    "        if root.right:\n",
    "            right_res = self.dfs(root.right, tree_map)\n",
    "            res = res + (\"+\" + right_res)\n",
    "        tree_map[res].append(root)\n",
    "        return res\n",
    "    \n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        tree_map = defaultdict(list)\n",
    "        res = self.dfs(root, tree_map)\n",
    "        res = []\n",
    "        \n",
    "        for rep, sub_roots in tree_map.items():\n",
    "            if len(sub_roots) >= 2:\n",
    "                res.append(sub_roots[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        subtree_dict = collections.defaultdict(int)\n",
    "        self.res = []\n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                return \"\"\n",
    "            left = traverse(root.left)\n",
    "            right = traverse(root.right)\n",
    "            sub_res = str(root.val) + \" \" + left + \" \" + right\n",
    "            subtree_dict[sub_res] += 1\n",
    "            if subtree_dict[sub_res] == 2:\n",
    "                self.res.append(root)\n",
    "            return sub_res\n",
    "        traverse(root)\n",
    "        return self.res\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        has = {}\n",
    "        ans=set()\n",
    "        def findastring(node,s=''):\n",
    "            if node is None:\n",
    "                return 'N'\n",
    "            elif node.left is None and node.right is None:\n",
    "                s+='m'+str(node.val)\n",
    "            else:\n",
    "                s+='m'+str(node.val)\n",
    "                s+=findastring(node.left)\n",
    "                s+=findastring(node.right)\n",
    "            if s not in has:\n",
    "                has[s]=node\n",
    "            else:\n",
    "                ans.add(has[s])\n",
    "            return s\n",
    "        findastring(root)\n",
    "        return list(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:\n",
    "        d = collections.defaultdict(list)\n",
    "        def dfs(root):\n",
    "            if not root: return ''\n",
    "            s = ' '.join([str(root.val), dfs(root.left), dfs(root.right)])\n",
    "            d[s].append(root)\n",
    "            return s\n",
    "        dfs(root)\n",
    "        return [l[0] for l in d.values() if len(l) > 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.node = ()\n",
    "        self.res_tmp = []\n",
    "        self.res = []\n",
    "\n",
    "    def postorder(self, root):\n",
    "        if not root:\n",
    "            return ''\n",
    "        left = self.postorder(root.left)\n",
    "        right = self.postorder(root.right)\n",
    "        link = str(root.val) + ',' + left + ',' + right\n",
    "        if link in self.node:\n",
    "            if link not in self.res_tmp:\n",
    "                self.res_tmp.append(link)\n",
    "                self.res.append(root)\n",
    "        else:\n",
    "            self.node += (link,)\n",
    "        return link\n",
    "    def findDuplicateSubtrees(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        self.postorder(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        d = collections.defaultdict(int)\n",
    "        res = []\n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                return '#'\n",
    "            l = traverse(root.left)\n",
    "            r = traverse(root.right)\n",
    "            signature = l + ',' + r + ',' + str(root.val)\n",
    "            if d[signature] == 1:\n",
    "                print(root.val)\n",
    "                res.append(root)\n",
    "            d[signature] += 1\n",
    "            return l + ',' + r + str(root.val)\n",
    "\n",
    "        traverse(root)\n",
    "        \n",
    "        return res\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# https://mp.weixin.qq.com/s/LJbpo49qppIeRs-FbgjsSQ\n",
    "# 跟序列化二叉树有关，序列化二叉树，就是把二叉树按照前或者中序或者后续遍历出来，写进字符串里\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        # 定义一个字典来存储所有子树以及出现的次数\n",
    "        self.memo = {}\n",
    "        # 定义一个列表来存储重复的子树根节点\n",
    "        self.res = []\n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "\n",
    "    # 辅助函数\n",
    "    def traverse(self, root):\n",
    "        if root is None:\n",
    "            return \"#\"\n",
    "        \n",
    "        left = self.traverse(root.left)\n",
    "        right = self.traverse(root.right)\n",
    "        \n",
    "        subTree = left + \",\" + right + \",\" + str(root.val)\n",
    "        \n",
    "        freq = self.memo.get(subTree, 0)\n",
    "        # 多次重复也只会被加入结果集一次\n",
    "        # 解释下这里==1的原因：第一次有subTree时，上一句代码将它初始化为0，然后self.memo[subTree] = freq + 1变为了1。\n",
    "        # 等到第二次，这个subTree又出现了（第二次出现），然后发现freq==1(上一次的)，这就说明重复出现了，好，把对应的root加进res。self.memo[subTree] = freq + 1变为2\n",
    "        # 等到第三次，freq已经变为2，不满足freq == 1的条件，不会加进res（因为之前已经加过了，这里就保证了不会重复）\n",
    "        if freq == 1:\n",
    "            self.res.append(root)\n",
    "        # 给子树对应的出现次数加一\n",
    "        self.memo[subTree] = freq + 1\n",
    "        # 这里不能用self.memo[subTree] += 1，因为第一次的时候subTree还不存在，会报错\n",
    "        return subTree\n",
    "\n",
    "\n",
    "\n",
    "# # 定义一个字典来存储所有子树以及出现的次数\n",
    "# memo = {}\n",
    "# # 定义一个列表来存储重复的子树根节点\n",
    "# res = []\n",
    "\n",
    "# # 主函数\n",
    "# def findDuplicateSubtrees(root):\n",
    "#     traverse(root)\n",
    "#     return res\n",
    "\n",
    "# # 辅助函数\n",
    "# def traverse(root):\n",
    "#     if root is None:\n",
    "#         return \"#\"\n",
    "    \n",
    "#     left = traverse(root.left)\n",
    "#     right = traverse(root.right)\n",
    "    \n",
    "#     subTree = left + \",\" + right + \",\" + str(root.val)\n",
    "    \n",
    "#     freq = memo.get(subTree, 0)\n",
    "#     # 多次重复也只会被加入结果集一次\n",
    "#     if freq == 1:\n",
    "#         res.append(root)\n",
    "#     # 给子树对应的出现次数加一\n",
    "#     memo[subTree] = freq + 1\n",
    "#     return subTree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        ans = []\n",
    "        if root is None:\n",
    "            return []\n",
    "        \n",
    "        root_dict = dict()\n",
    "        def fun(root):\n",
    "            if root is None:\n",
    "                return '#'\n",
    "            \n",
    "            cur_sub = str(root.val) + ',' + fun(root.left) + ',' + fun(root.right)\n",
    "            if cur_sub not in root_dict:\n",
    "                #print('cur sub is :', cur_sub)\n",
    "                root_dict[cur_sub] = root\n",
    "            else:\n",
    "                nonlocal ans\n",
    "                if root_dict[cur_sub] not in ans:\n",
    "                    ans.append(root_dict[cur_sub])\n",
    "            \n",
    "            return cur_sub\n",
    "\n",
    "        \n",
    "        fun(root)\n",
    "        print('ans is: ', ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        res = []\n",
    "        def serilaze(root, res) -> str:\n",
    "            if root is None:\n",
    "                res += ' ,'\n",
    "                return res\n",
    "            else:\n",
    "                res += str(root.val)\n",
    "                res += ','\n",
    "                return res + serilaze(root.left, '') + serilaze(root.right, '')\n",
    "        dic = {}\n",
    "        print(serilaze(root, ''))\n",
    "        def traversal(root) -> None:\n",
    "            if root is None:\n",
    "                return \n",
    "            if serilaze(root, '') not in dic:\n",
    "                dic[serilaze(root, '')] = root\n",
    "            else:\n",
    "                res.append(dic[serilaze(root, '')])\n",
    "            traversal(root.left)\n",
    "            traversal(root.right)\n",
    "        traversal(root)\n",
    "        return set(res)\n",
    "         \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, node: Optional[TreeNode]):\n",
    "        if node == None:\n",
    "            return [\"#\"]\n",
    "        left_path = self.dfs(node.left)\n",
    "        right_path = self.dfs(node.right)\n",
    "        path = left_path + right_path + [f\"{node.val}\"]\n",
    "        path_str = \" \".join(path)\n",
    "        if path_str not in self.hash_set:\n",
    "            self.hash_set.add(path_str)\n",
    "        else:\n",
    "            self.ans[path_str] = node\n",
    "        return path\n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.hash_set = set()\n",
    "        self.ans = dict()\n",
    "        self.dfs(root)\n",
    "        return list(v for v in self.ans.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        def serialze(node):\n",
    "            nonlocal vis, res\n",
    "            if not node:\n",
    "                return ''\n",
    "            \n",
    "            s = str(node.val) + '(' + serialze(node.left) + ')(' + serialze(node.right) + ')'\n",
    "            if s in vis and vis[s] == 1:\n",
    "                res.append(node)\n",
    "            vis[s] += 1\n",
    "            return s\n",
    "\n",
    "        vis = defaultdict(int)\n",
    "        res = []\n",
    "        serialze(root)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        def dfs(node: Optional[TreeNode]) -> str:\n",
    "            if not node:\n",
    "                return \"\"\n",
    "            \n",
    "            serial = \"\".join([str(node.val), \"(\", dfs(node.left), \")(\", dfs(node.right), \")\"])\n",
    "            if (tree := seen.get(serial, None)):\n",
    "                repeat.add(tree)\n",
    "            else:\n",
    "                seen[serial] = node\n",
    "            return serial\n",
    "        \n",
    "        seen = dict()\n",
    "        repeat = set()\n",
    "\n",
    "        dfs(root)\n",
    "        return list(repeat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return \"\"\n",
    "            line = \"\".join([str(node.val), \"(\", dfs(node.left), \")(\", dfs(node.right), \")\"])\n",
    "            if (tree := seen.get(line, None)):\n",
    "                repeat.add(tree)\n",
    "            else:\n",
    "                seen[line] = node\n",
    "            return line\n",
    "\n",
    "        seen = {}\n",
    "        repeat = set()\n",
    "        dfs(root)\n",
    "        return list(repeat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "\n",
    "        def dfs(node: TreeNode):\n",
    "            if not node:\n",
    "                return \"\"\n",
    "            else:\n",
    "                s = str(node.val)+f\"({dfs(node.left)})({dfs(node.right)})\"\n",
    "                if hs[s] and s not in nret:\n",
    "                    nret.add(s)\n",
    "                    ret.add(node)\n",
    "                else:\n",
    "                    hs[s] = True\n",
    "                return s\n",
    "\n",
    "        hs = defaultdict(lambda: False)\n",
    "        nret = set()\n",
    "        ret = set()\n",
    "        dfs(root)\n",
    "        return list(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def traverse(self, root, subtree_map):\n",
    "        if root is None:\n",
    "            return \"N\"\n",
    "        l_ret = self.traverse(root.left, subtree_map)\n",
    "        r_ret = self.traverse(root.right, subtree_map)\n",
    "        if l_ret != \"N\" and l_ret != \"(N#N)\":\n",
    "            if l_ret not in subtree_map:\n",
    "                subtree_map[l_ret] = []\n",
    "            subtree_map[l_ret].append(root.left)\n",
    "        if r_ret != \"N\" and r_ret != \"(N#N)\":\n",
    "            if r_ret not in subtree_map:\n",
    "                subtree_map[r_ret] = []\n",
    "            subtree_map[r_ret].append(root.right)\n",
    "        #print(subtree_map)\n",
    "        ret = f\"({l_ret}#{root.val}#{r_ret})\"\n",
    "        return ret\n",
    "        \n",
    "\n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        subtree_map = {}\n",
    "        self.traverse(root, subtree_map)\n",
    "        dup_subtrees = []\n",
    "        for k in subtree_map:\n",
    "            if len(subtree_map[k]) > 1:\n",
    "                dup_subtrees.append(subtree_map[k][0])\n",
    "        return dup_subtrees\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "\n",
    "\n",
    "        self.dic = {}\n",
    "        self.res = []\n",
    "\n",
    "        def func(root):\n",
    "            if not root:\n",
    "                return '#'\n",
    "            left = func(root.left)\n",
    "            right = func(root.right)\n",
    "            s = f\"{left}, {right}, {root.val}\"\n",
    "\n",
    "            freq = self.dic.get(s, 0)\n",
    "            if freq == 1:\n",
    "                self.res.append(root)\n",
    "            self.dic[s] = freq+1\n",
    "            return s \n",
    "\n",
    "        func(root)\n",
    "        return self.res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        res_dict = {}\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return ''\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            pre = str(root.val) + 'l' + left + 'r' + right\n",
    "            mid = 'l' + left + str(root.val) + 'r' + right\n",
    "\n",
    "            key = pre + '_' + mid\n",
    "            if key not in res_dict:\n",
    "                res_dict[key] = [root]\n",
    "            else:\n",
    "                res_dict[key].append(root)\n",
    "\n",
    "            return pre\n",
    "\n",
    "        \n",
    "        dfs(root)\n",
    "        for value in res_dict.values():\n",
    "            if len(value) >= 2:\n",
    "                res.append(value[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        res_dict = {}\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return ''\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            pre = str(root.val) + 'l' + left + 'r' + right\n",
    "            mid = 'l' + left + str(root.val) + 'r' + right\n",
    "\n",
    "            key = pre + '_' + mid \n",
    "            if len(res_dict.get(key, [])) == 1:\n",
    "                res.append(root)\n",
    "            if key not in res_dict:\n",
    "                res_dict[key] = [root]\n",
    "            else:\n",
    "                res_dict[key].append(root)\n",
    "\n",
    "            return pre\n",
    "\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.count = {}\n",
    "        self.res = []\n",
    "        self.dfs(root)\n",
    "        return self.res\n",
    "    \n",
    "    def dfs(self, root):\n",
    "        if not root:\n",
    "            return 'null,'\n",
    "        rep = f'{root.val},'\n",
    "        rep += self.dfs(root.left)\n",
    "        rep += self.dfs(root.right)\n",
    "        self.count[rep] = self.count.get(rep, 0) + 1\n",
    "        if self.count[rep] == 2:\n",
    "            self.res.append(root)\n",
    "        return rep\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "\n",
    "        \"\"\"\n",
    "        回傳重複的 tree (數值和結構要一樣)\n",
    "        1. 如果 tree 的架構是一樣的, 那它的 subtree 架構也是一樣的\n",
    "           [2, 4] subtree\n",
    "           [4]    subtree 的 subtree\n",
    "        \"\"\"\n",
    "\n",
    "        \"\"\"\n",
    "        暴力法: O(n^3)\n",
    "        如果要每個 node 都走過一次\n",
    "        每個 subtree 都要走過一次, 都要比過一次\n",
    "        \"\"\"\n",
    "\n",
    "        \"\"\"\n",
    "        把 tree 變成一個\"字串\"\n",
    "\n",
    "        1. 對每個 subtree 都把它變成一個 string (serialization)\n",
    "\n",
    "        2. 用 preorder (其他也可以)\n",
    "\n",
    "        3. 用 hashmap 紀錄每個 subtree\n",
    "           (key 就是 subtree 的 string)\n",
    "           如果一個 key 有兩個 node, 那就代表這個 subtree 是重複的\n",
    "\n",
    "        4. 從 root 開始執行 dfs, 建立每個 subtree 的 string\n",
    "           (要把 \"null\" 的部分加進去, 這樣才能把 subtree \"結構\"做出來)\n",
    "            \n",
    "            e.g. 同樣是 1, 2, 3, 但是兩個 subtree 架構都不一樣!\n",
    "            a. [1, 2, Null, Null, 3, Null, Null]\n",
    "            b. [1, Null, 2, Null, 3, Null, Null]\n",
    "\n",
    "        5. time: O(n*n)\n",
    "           有 n 個 node, 每個 node 都要做出 n 個 string(最大)\n",
    "        \"\"\"\n",
    "\n",
    "        # 想到這招真的很厲害...\n",
    "        hashmap = defaultdict(list)\n",
    "        result  = []\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return \"null\"\n",
    "\n",
    "            s = str(node.val) + \",\" + dfs(node.left) + \",\" + dfs(node.right)\n",
    "\n",
    "            # 如果這個 string 已經在 hashmap 裡面了\n",
    "            if len(hashmap[s]) == 1:\n",
    "                result.append(node) # 把當前的 node 當作 root 加入到 result\n",
    "            hashmap[s].append(node) # 也加入到 hashmap 對應的 string\n",
    "            print(f\"{s=}\")\n",
    "            return s\n",
    "        \n",
    "        dfs(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "\n",
    "        \"\"\"\n",
    "        回傳重複的 tree (數值和結構要一樣)\n",
    "        1. 如果 tree 的架構是一樣的, 那它的 subtree 架構也是一樣的\n",
    "           [2, 4] subtree\n",
    "           [4]    subtree 的 subtree\n",
    "        \"\"\"\n",
    "\n",
    "        \"\"\"\n",
    "        暴力法: O(n^3)\n",
    "        如果要每個 node 都走過一次\n",
    "        每個 subtree 都要走過一次, 都要比過一次\n",
    "        \"\"\"\n",
    "\n",
    "        \"\"\"\n",
    "        把 tree 變成一個\"字串\"\n",
    "\n",
    "        1. 對每個 subtree 都把它變成一個 string (serialization)\n",
    "\n",
    "        2. 用 preorder (其他也可以)\n",
    "\n",
    "        3. 用 hashmap 紀錄每個 subtree\n",
    "           (key 就是 subtree 的 string)\n",
    "           如果一個 key 有兩個 node, 那就代表這個 subtree 是重複的\n",
    "\n",
    "        4. 從 root 開始執行 dfs, 建立每個 subtree 的 string\n",
    "           (要把 \"null\" 的部分加進去, 這樣才能把 subtree \"結構\"做出來)\n",
    "            \n",
    "            e.g. 同樣是 1, 2, 3, 但是兩個 subtree 架構都不一樣!\n",
    "            a. [1, 2, Null, Null, 3, Null, Null]\n",
    "            b. [1, Null, 2, Null, 3, Null, Null]\n",
    "\n",
    "        5. time: O(n*n)\n",
    "           有 n 個 node, 每個 node 都要做出 n 個 string(最大)\n",
    "        \"\"\"\n",
    "\n",
    "        # 想到這招真的很厲害...\n",
    "        hashmap = defaultdict(list)\n",
    "        result  = []\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return \"null\"\n",
    "\n",
    "            s = str(node.val) + \",\" + dfs(node.left) + \",\" + dfs(node.right)\n",
    "\n",
    "            # 如果這個 string 已經在 hashmap 裡面了\n",
    "            if len(hashmap[s]) == 1:\n",
    "                result.append(node) # 把當前的 node 當作 root 加入到 result\n",
    "            hashmap[s].append(node) # 也加入到 hashmap 對應的 string\n",
    "            print(f\"{s=}\")\n",
    "            return s\n",
    "        \n",
    "        dfs(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        history = {}\n",
    "        ans = []\n",
    "        def search(root, history, ans):\n",
    "            if root == None:\n",
    "                return 'n '\n",
    "            else:\n",
    "                s = ''\n",
    "                s += str(root.val) + ' '\n",
    "                s += search(root.left, history, ans) + ' '\n",
    "                s += search(root.right, history, ans) + ' '\n",
    "\n",
    "                # print(s)\n",
    "                if s in history:\n",
    "                    if history[s] == 1:\n",
    "                        ans.append(root)\n",
    "                    history[s] += 1\n",
    "                else:\n",
    "                    history[s] = 1\n",
    "                \n",
    "                return s\n",
    "        \n",
    "        search(root, history, ans)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        global visited_node \n",
    "        visited_node = set()\n",
    "        global overlap_root_node\n",
    "        overlap_root_node = dict()\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return \n",
    "            string_treenode = f'{root.val}({dfs(root.left)},{dfs(root.right)})'\n",
    "            if string_treenode in visited_node:\n",
    "                overlap_root_node[string_treenode] = (root)\n",
    "            else:\n",
    "                visited_node.add(string_treenode)\n",
    "            #print(string_treenode)\n",
    "            return string_treenode\n",
    "        \n",
    "        dfs(root)\n",
    "        #print(overlap_root_node)\n",
    "\n",
    "        return list(overlap_root_node.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.dct = {}\n",
    "        self.dfs(root)\n",
    "        return [v[0] for v in self.dct.values() if len(v) > 1]\n",
    "\n",
    "    \n",
    "    def dfs(self, head):\n",
    "        if not head:\n",
    "            return \"(#)\"\n",
    "        \n",
    "        ret = str(head.val)\n",
    "\n",
    "        ret = ret + self.dfs(head.left) \n",
    "        ret = ret + self.dfs(head.right)\n",
    "\n",
    "        ret = f\"({ret})\"\n",
    "        if ret not in self.dct:\n",
    "            self.dct[ret] = []\n",
    "        self.dct[ret].append(head)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        d={}\n",
    "        ans=[]\n",
    "        if not root: return []\n",
    "        def dfs(root):\n",
    "            if not root: return ''\n",
    "            left=dfs(root.left)\n",
    "            right=dfs(root.right)\n",
    "            chain=left+','+right+','+str(root.val)\n",
    "            if chain not in d:\n",
    "                d[chain]=1\n",
    "            else:\n",
    "                d[chain]+=1\n",
    "            if d[chain]==2:\n",
    "                ans.append(root)\n",
    "            return chain\n",
    "        tree=dfs(root)\n",
    "        print(tree)\n",
    "        print(d)\n",
    "        return ans\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.ans = []\n",
    "        self.cnt = defaultdict(int)\n",
    "        # @lru_cache(None)\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 'None'\n",
    "            node = f'{root.val}, {dfs(root.left)}, {dfs(root.right)}'\n",
    "            self.cnt[node] += 1   \n",
    "            if self.cnt[node] == 2:\n",
    "                self.ans.append(root)                     \n",
    "            return node\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.treeNodeMap = {}\n",
    "        self.treeNodeSet = []    \n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        \n",
    "        self.visitTreeNode(root)\n",
    "        return list(self.treeNodeMap.values())\n",
    "        \n",
    "\n",
    "    \n",
    "\n",
    "    def visitTreeNode(self, node):\n",
    "        if node is None:\n",
    "            return None\n",
    "        \n",
    "        treeNodeKey = f'{node.val}_({self.visitTreeNode(node.left)}_{self.visitTreeNode(node.right)})'\n",
    "        if treeNodeKey in self.treeNodeSet:\n",
    "            self.treeNodeSet.append(treeNodeKey)\n",
    "            self.treeNodeMap[treeNodeKey] = node\n",
    "        else:\n",
    "            self.treeNodeSet.append(treeNodeKey)\n",
    "\n",
    "\n",
    "        return treeNodeKey\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
